# 括号生成：https://leetcode-cn.com/problems/generate-parentheses/submissions/

# 再次写，这几个月还是有收获的，一次写出来
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        """
            有n对括号，求所有的正确组合
        """
        rst = []
        def create(s, left, right):
            if right > left:
                return
            if left + right > 2 * n:
                return
            if left == right and left == n:
                rst.append(s)
                return
            
            create(s + "(", left + 1, right)
            create(s + ")", left, right + 1)
        
        create("", 0, 0)
        return rst


# 还可以这样写 剪枝

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        """
            有n对括号，求所有的正确组合
        """
        rst = []
        def create(s, left, right):
            
            if left + right  == 2 * n:
                rst.append(s)
                return
            
            if left < n:
                create(s + "(", left + 1, right)
            if right < left:
                create(s + ")", left, right + 1)
        
        create("", 0, 0)
        return rst